Sorry, your browser cannot access this site
This page requires browser support (enable) JavaScript
Learn more >

P1880 [NOI1995] 石子合并

一道区间dp题目。

d[i][j] 表示从 ij 的最大/最小得分,那么依次枚举长度 len,坐标 ij,三层循环就可以 dp递推求得最值了。

(如果没有环的话)

不要着急,我们将序列复制一遍接到后面做一遍即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<ctype.h>
#define INF 0x3f3f3f3f
using namespace std;
inline int read()
{
int x=0,w=1;char c=getchar();
while(!isdigit(c)){
if(c=='-')w=-1;
c=getchar();
}
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*w;
}
const int maxn=105*2;
int a[maxn],sum[maxn],d[maxn][maxn],d2[maxn][maxn];
int main()
{
int n=read();
for(int i=1;i<=n;i++)a[i]=a[i+n]=read();
for(int i=1;i<=(n+n);i++)sum[i]=sum[i-1]+a[i];//前缀和
for(int len=2;len<=n;len++)
for(int i=1,j=i+len-1;i<n+n and j<n+n ;i++,j=i+len-1)
{
d[i][j]=INF;
for(int k=i;k<j;k++)
{
if(d[i][j]>d[i][k]+d[k+1][j]+sum[j]-sum[i-1])
d[i][j]=d[i][k]+d[k+1][j]+sum[j]-sum[i-1];
if(d2[i][j]<d2[i][k]+d2[k+1][j]+sum[j]-sum[i-1])
d2[i][j]=d2[i][k]+d2[k+1][j]+sum[j]-sum[i-1];
}

}
int ans1=INF,ans2=0;
for(int i=1;i<=n;i++)ans1=min(ans1,d[i][i+n-1]),ans2=max(ans2,d2[i][i+n-1]);
printf("%d\n%d\n",ans1,ans2);
return 0;
}

如果数据再大一点的话,需要用到平行四边形优化。


扩展:这道题的数据范围是 \(n\leq 100\) ,而我们给它还扩充到了 \(n\leq 200\)。那么如果n更大呢?比如 \(n\leq 40000\)

这里有一道题目P5569 [SDOI2008] 石子合并

是的我们没法再用 40000*40000 的 DP 做了。

有兴趣可以去看题解。

给小狼留言